package leetcode_800;

import java.util.LinkedList;
import java.util.Queue;

/**
 *@author 周杨
 *IsGraphBipartite_785 一个无向图能否被分成2分图 即每条边的节点都在不同的两个子集里
 *describe:用广度优先遍历 每遇到一个节点就上色 看附近的是否是一样的颜色 AC 80%
 *2018年10月22日 上午10:32:44
 */
public class IsGraphBipartite_785 {
	public boolean isBipartite(int[][] graph) {
        int[] visited = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (graph[i].length != 0 && visited[i] == 0) {
                visited[i] = 1;
                Queue<Integer> q = new LinkedList<>();
                q.offer(i);
                while(! q.isEmpty()) {//循环上色 直到联通的节点都被上色
                    int current = q.poll();
                    for (int c: graph[current]) {
                            if (visited[c] == 0) {
                                visited[c] = (visited[current] == 1) ? 2 : 1;
                                q.offer(c);
                            } else {
                                if (visited[c] == visited[current]) return false;
                            }
                    }
                }                        
                
            }
        }
        return true;
    }
}
